Problem

咋一看这题目名字怎么那么亲切，结果看到题面就觉得不亲切了（大雾）
原题传送门
Description
给定整数$N$，求$1<=x,y<=N$且$gcd(x,y)$为素数的数对$(x,y)$有多少对.

Input
一个整数$N$

Output
如题

Sample Input
4

Sample Output
4

HINT
对于样例$(2,2),(2,4),(3,3),(4,2)$

$1<=N<=10^7$

Solution

按照~~网上流传~~的说法，此题为欧拉函数练手题
解法确实也很好懂，下面做一下详细的解释：

首先，定义集合$P=\{x|x为素数\}$，接下来我们可以得出:

$∀p∈P,∃k_1,k_2满足gcd(k1,k2) = 1,gcd(k1·p,k2·p) = p$

①若$k_1≠k_2$
令$k_1>k_2$
则满足调节的$k_1$的个数就为$φ(k_1)$
∴$k_1,k_2$所构成的组合的个数为$2·φ(k_1)$
②若$k_1=k_2$
当且仅当$k_1=k_2=1$时，满足条件

综上，满足条件的所有数对个数为$\Sigma_{p∈P}^{n}[(\Sigma_{i=1}^{\lfloor\frac{n}{p}\rfloor}2φ(i))+1]$

推到这一步，我们会惊讶地发现
woc这时间复杂度已经爆表了啊。。
没事，我们来看看哪里爆了。。。
诶？似乎没爆？

==>睁大眼睛好好看看$φ(N)$的计算公式：

时间复杂度为标准的$O(n\sqrt{n})$，完美超时
下面介绍3个很奇妙的东西

当$p∈P$(也就是P为质数)时，$φ(p) = p-1$
若$i\ mod\ p =\ 0$, 那么$φ(i·p)=p·φ(i)$
若$i\ mod\ p ≠\ 0$, 那么$φ(i·p)=φ(i)·( p-1 )$

这些都是欧拉函数的一些很奇妙的性质（证明就不管它了）
利用这些性质，我们就可以在$O(n)$内搞出所有$φ$值了
算完了$φ$值，会发现还有一个和要维护，不然还是会T。这个简单，前缀和即可。
总时间复杂度$O(n)$
下面给出了带有详细注释的代码：

#include <iostream>
#include <cstring>
#include <cstdlib>
#define MAXN 10000000 + 5
using namespace std;
int N;
long long Phi[MAXN], p[MAXN], pt;
bool flag[MAXN];
long long sum[MAXN];
inline void getphi()
{
	pt = 0;
	Phi[1] = 1;
	for (register int i = 2; i <= N; i++)
	{
		if (!flag[i])									//这表明了i是素数 
		{
			p[++pt] = i;
			Phi[i] = i - 1;								//如果i是素数，那么phi(i) = p - 1; 
		}
		for (register int j = 1; j <= pt && p[j] * i <= N; j++)
		{
			int k = p[j] * i;
			flag[k] = true;								//k可以通过乘积的形式得到，当然就不是素数了。于是标记改为true 
			if (i % p[j] == 0)
			{
				Phi[k] = p[j] * Phi[i];					//如果i mod p = 0, 那么 phi(i * p) = p * phi(i)
				break;
			} else
			{
				Phi[k] = (p[j] - 1) * Phi[i];			//积性函数的性质 :若i mod p ≠0, 那么 phi(i * p)=phi(i) * (p - 1) 
			}
		}
	}
}
int main(int argc, char **argv)
{
	ios::sync_with_stdio(false);
	cin >> N;
	getphi();
	memset(sum, 0, sizeof sum);
	sum[1] = 1;
	for (register int i = 2; i <= N; ++i)
	{
		sum[i] = sum[i - 1] + 2 * Phi[i];
	}
	long long ans = 0;
	for (register int i = 1; i <= pt; ++i)
	{
		ans += sum[(int)(N / p[i])];
	}
	cout << ans << endl;
	return 0;
}